#include <algorithm>
#include <climits>
#include <cstdio>
#include <iostream>
#include <unordered_set>
#include <vector>

/**
 * Luogu P1073: Optimal Trade
 * The following solution uses union-find and DFS. It has time complexity O(V +
 * E). However, it still exceeds time limit on four cases.
 */

struct Vertex {
    int root;
    int maxPrice, minPrice;
    std::unordered_set<int> edges;

    Vertex(int idx, int price) : root(idx), maxPrice(price), minPrice(price) {}
};

std::vector<Vertex> vertices;

int find(int idx) {
    Vertex &v = vertices[idx];
    if (v.root != idx) v.root = find(v.root);
    return v.root;
}

void union_(int i1, int i2) {
    int r1 = find(i1), r2 = find(i2);
    if (r1 > r2) std::swap(r1, r2);
    vertices[r2].root = r1;
}

int maxProfit = 0;
std::vector<bool> visited;

void search(int idx, int buyPrice, int profit) {
    // Record this vertex
    if (visited[idx]) return;
    visited[idx] = true;

    // Update buy price and profit
    Vertex &v = vertices[idx];
    buyPrice = std::min(buyPrice, v.minPrice);
    profit = std::max(profit, v.maxPrice - buyPrice);

    static const int fin = find(vertices.size() - 1);
    if (idx == fin) {
        // Update profits of this path if destination is reached
        maxProfit = std::max(maxProfit, profit);
    } else {
        // Add successors to path
        for (auto to : vertices[idx].edges) search(find(to), buyPrice, profit);
    }

    // Pop this vertex
    visited[idx] = false;
}

int main() {
    // Input
    int nVerts, nEdges;
    scanf("%d %d", &nVerts, &nEdges);
    for (int i = 0; i < nVerts; i++) {
        int price;
        scanf("%d", &price);
        vertices.push_back(Vertex(i, price));
    }
    for (int i = 0; i < nEdges; i++) {
        int from, to, dir;
        scanf("%d %d %d", &from, &to, &dir);
        from--, to--;
        if (dir == 1)
            vertices[from].edges.insert(to);
        else
            union_(from, to);
    }

    // Shrink vertices in an equivalent class to a single one
    for (int i = 0; i < nVerts; i++) {
        Vertex &v = vertices[i];
        if (v.root == i) continue;
        int ri = find(i);
        Vertex &r = vertices[ri];
        r.maxPrice = std::max(r.maxPrice, v.maxPrice);
        r.minPrice = std::min(r.minPrice, v.minPrice);
        r.edges.insert(v.edges.begin(), v.edges.end());
        v.edges.clear();
    }

    // DFS the graph to find best path
    visited = std::vector<bool>(nVerts, false);
    search(0, INT_MAX, 0);
    printf("%d\n", maxProfit);

    return 0;
}

/**
 * The following solution exceeds time limit on four cases.
 * The complexity of this solution is O(V^2), which may take too much time on
 * large graphs.
 */

/*
struct Vertex {
    int price;
    std::vector<int> succ, pred;
};

std::vector<Vertex> vertices;

void searchFwd(int idx, std::vector<bool> &visited) {
    visited[idx] = true;
    Vertex &v = vertices[idx];
    for (int i = 0; i < v.succ.size(); i++) {
        int to = v.succ[i];
        if (visited[to]) continue;
        searchFwd(to, visited);
    }
}

void searchBwd(int idx, std::vector<bool> &visited) {
    visited[idx] = true;
    Vertex &v = vertices[idx];
    for (int i = 0; i < v.pred.size(); i++) {
        int to = v.pred[i];
        if (visited[to]) continue;
        searchBwd(to, visited);
    }
}

int main() {
    // Input
    int nVerts, nEdges;
    scanf("%d %d", &nVerts, &nEdges);
    for (int i = 0; i < nVerts; i++) {
        Vertex vert;
        scanf("%d", &vert.price);
        vertices.push_back(vert);
    }
    for (int i = 0; i < nEdges; i++) {
        int from, to, dir;
        scanf("%d %d %d", &from, &to, &dir);
        from--, to--;
        vertices[from].succ.push_back(to);
        vertices[to].pred.push_back(from);
        if (dir == 2) {
            vertices[to].succ.push_back(from);
            vertices[from].pred.push_back(to);
        }
    }

    // DFS to find possible buy and sell places
    std::vector<bool> canBuy(nVerts, false), canSell(nVerts, false);
    searchFwd(0, canBuy);
    searchBwd(nVerts - 1, canSell);

    // Check all possible 1 -> buy -> sell -> n path
    int profit = 0;
    for (int i = 0; i < nVerts; i++) {
        if (!canBuy[i]) continue;
        Vertex &buyCity = vertices[i];
        std::vector<bool> buyReachable(nVerts, false);
        searchFwd(i, buyReachable);
        for (int j = 0; j < nVerts; j++) {
            if (!canSell[j] || !buyReachable[j]) continue;
            profit = std::max(profit, vertices[j].price - vertices[i].price);
        }
    }
    printf("%d\n", profit);

    return 0;
}
*/